#include <stdio.h>
#include <stdlib.h>
#include "Sort.h"

#define SIZE 10


void show(ElementType item[], int n) {
    printf("[");
    for (int i = 0; i < n; ++i) {
        printf("%d", item[i]);
        if (i < n - 1) {
            printf(",");
        }
    }
    printf("]\n");
}

void bubbleSort(ElementType item[], int n) {
    int k = n - 1, pos = 0;
    for (int i = 0; i < n - 1; ++i) {
        // 第一次优化，当内循环没有交换的时候表示已经是有序的
        int flag = 1;
        for (int j = 0; j < k; ++j) {
            if (item[j] > item[j + 1]) {
                ElementType temp = item[j + 1];
                item[j + 1] = item[j];
                item[j] = temp;
                flag = 0;
                // 第二次优化，记下最后一次交换记录的位置
                pos = j;
            }
        }
        // 内循环只需要遍历到最后一次交换记录的位置
        k = pos;
        if (flag) {
            break;
        }
    }

    printf("冒泡排序: ");
    show(item, n);
}

void insertSort(ElementType item[], int n) {
    for (int i = 1; i < n; ++i) {
        int temp = item[i];
        // 存在比当前元素大的，一直往后移动
        int j = i - 1;
        while (j >= 0 && item[j] > temp) {
            item[j + 1] = item[j];
            --j;
        }
        item[j + 1] = temp;
    }

    printf("插入排序: ");
    show(item, n);

}

void shellSort(ElementType item[], int n) {
    // 增量间隔
    int gap = n / 2;
    while (gap > 0) {
        // 采用插入排序
        for (int i = gap; i < n; i++) {
            int temp = item[i];
            int j = i - gap;
            while (j >= 0 && item[j] > temp) {
                item[j + gap] = item[j];
                j = j - gap;
            }
            item[j + gap] = temp;
        }
        gap = gap / 2;
    }

    printf("希尔排序: ");
    show(item, n);
}

void selectSort(ElementType item[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int k = i;
        for (int j = i + 1; j < n; ++j) {
            if (item[j] < item[k]) {
                k = j;
            }
        }
        if (k != i) {
            int temp = item[i];
            item[i] = item[k];
            item[k] = temp;
        }
    }

    printf("直接选择排序: ");
    show(item, n);
}

void sift(ElementType item[], int low, int high) {
    // item[j]是item[i]的左孩子
    int i = low, j = 2 * i;
    int temp = item[i];
    while (j <= high) {
        if (j < high && item[j] < item[j + 1]) {
            j++;
        }
        if (temp < item[j]) {
            item[i] = item[j];
            i = j;
            j = 2 * i;
        } else {
            break;
        }
    }
    item[i] = temp;
}

void heapSorts(ElementType item[], int n) {
    // 建立初始化堆
    for (int i = n / 2; i >= 1; --i) {
        sift(item, i, n);
    }
    for (int i = n; i >= 2; --i) {
        int temp = item[1];
        item[1] = item[i];
        item[i] = temp;
        sift(item, 1, i - 1);
    }

    printf("堆排序: ");
    show(item, n);
}

void merges(ElementType item[], int low, int mid, int high) {
    ElementType *temp = malloc((high - low + 1) * sizeof(ElementType));
    // k 是temp的下标，i,j分别第1,2段的下标
    int i = low, j = mid + 1, k = 0;
    // 在第1段和第2段均未扫描完时循环
    while (i <= mid && j <= high) {
        // 将第1段中的记录放入temp中
        if (item[i] < item[j]) {
            temp[k] = item[i];
            i++;
            k++;
        } else {
            // 将第2段中的记录放入temp中
            temp[k] = item[j];
            j++;
            k++;
        }
    }
    // 将第1段余下的部分复制到temp中
    while (i < mid) {
        temp[k] = item[i];
        i++;
        k++;
    }
    // 将第2段余下的部分复制到temp中
    while (j <= high) {
        temp[k] = item[j];
        j++;
        k++;
    }
    // 将temp复制回item中
    for (k = 0, i = low; i <= high; k++, i++) {
        item[i] = temp[k];
    }
}

// 对整个数列进行一趟归并
void mergePass(ElementType item[], int length, int n) {
    int i;
    // 归并length 长的两相邻子表
    for (i = 0; i + 2 * length - 1 < n; i = i + 2 * length) {
        merges(item, i, i + length - 1, i + 2 * length - 1);
    }
    // 余下两个子表，后者长度小于length
    if (i + length - 1 < n) {
        // 归并这两个子表
        merges(item, i, i + length - 1, n - 1);
    }
}

// 自底向上的二路归并算法
void mergeSort(ElementType item[], int n) {
    for (int length = 1; length < n; length *= 2) {
        mergePass(item, length, n);
    }

    printf("归并排序: ");
    show(item, n);
} 

void testSort() {
    ElementType item[] = {1, 5, 6, 7, 8, 0, 9, 4, 3, 2};
    printf("原元素: ");
    show(item, SIZE);
    bubbleSort(item, SIZE);
    insertSort(item, SIZE);
    shellSort(item, SIZE);
    selectSort(item, SIZE);
    heapSorts(item, SIZE);
    mergeSort(item, SIZE);
}
